#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

/**
  * @方法: 递归
  * @时间复杂度: o(m + n)
  * @空间复杂度: o(m + n)
  * @评价:
*/
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    if(list1 == nullptr) return list2;
    if(list2 == nullptr) return list1;
    if(list1->val <= list2->val){
        ListNode* p = list1->next;
        list1->next = mergeTwoLists(p, list2);
        return list1;
    }else{
        ListNode* p = list2->next;
        list2->next = mergeTwoLists(p, list1);
        return list2;
    }
}


/**
  * @方法: 双指针
  * @时间复杂度: o(m + n)
  * @空间复杂度: o(1)
  * @评价:
*/
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    if(list1 == nullptr) return list2;
    if(list2 == nullptr) return list1;

    ListNode* dummy = new ListNode(-1);
    ListNode* p = dummy;

    ListNode* p1 = list1;
    ListNode* p2 = list2;

    while(p1 != nullptr && p2 != nullptr){
        if(p1->val <= p2->val){
            p->next = p1;
            p1 = p1->next;
        }else{
            p->next = p2;
            p2 = p2->next;
        }
        p = p->next;
    }
    if(p1 == nullptr){
        p->next = p2;
    }else{
        p->next = p1;
    }
    return dummy->next;
}

int main(){
    cout << "hello world" << endl;
    return 0;
}